/**
* @description: 808. 分汤
* @author hewei
* @date 2022/9/7 14:41
* @version 1.0
*/

public class SoupServings {

    public double soupServings(int n) {
        n = n / 25 + (n % 25 == 0 ? 0 : 1);
        if (n >= 200) return 1;

        double[][] dp = new double[n + 1][n + 1];
        dp[0][0] = 0.5;
        for (int i = 1; i < n + 1; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] += dp[Math.max(0, i - 4)][j];
                dp[i][j] += dp[Math.max(0, i - 3)][Math.max(0, j - 1)];
                dp[i][j] += dp[Math.max(0, i - 2)][Math.max(0, j - 2)];
                dp[i][j] += dp[Math.max(0, i - 1)][Math.max(0, j - 3)];
                dp[i][j] /= 4.0;
            }
        }
        return dp[n][n];
    }
}
